PTA1001总结
考点
- 字符串处理
- 输入输出
问题重述
c++
A_plus_B_Format.py
代码详情
1 |
|
A_plus_B_Format.cpp
代码详情
1 | // |
data.json
代码详情
1 |
PTA1002总结
考点
- 字符串处理
- 输入输出
问题重述
python
坑点1:
需要考虑到多项式的值为0的时候,输出为"0"不能有空格"0 "
测试数据中的某个测试点的输出格式错误的测试数据
坑点2:
记得考虑到所有的值都被round了
对应到我的代码中:这个地方也需要round
测试数据中的测试点1
思路
$\xrightarrow{\text{summit}}$读取输入的字符串$\xrightarrow{\text{rectify_data}}$得到的中间数据结构$\xrightarrow{\text{cal_poly}}$得到中间数据结构表示的计算的结果$\xrightarrow{\text{rectify_str}}$得到符合题目要求的正确结果$\xrightarrow{\text{summit}}$输出
语法技术
keys()不能进行+运算
sum的特殊用法
range() takes no keyword arguments
拓展阅读
四舍五入
A_plus_B_for_Polynomials.py
代码详情
1 | from typing import Dict |
A_plus_B_for_Polynomials.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1003总结
考点
- 图
- 最短路径
- Dijkstra
- 图
- 最短路径
- 无向图
- 带权图
- 全连通图
- 单源最短路径
- Dijkstra算法
- 邻接矩阵
问题重述
python
第一次提交
错误原因没有考虑经过$\color{green}{\text{前面一个点}}$到$\color{red}{\text{现在这个点}}$需要加上到$\color{green}{\text{前面一个点}}$的路径数(见data.json中的第三个测试数据)
第二次提交
去掉typing和unittest
包含typing和unittest
java
测试点情况
思路
做一次dijkstra,删一次路径
语法技术
拓展阅读
Emergency.py
代码详情
1 | from typing import Dict, List |
data.json
代码详情
1 | [ |
PTA1004总结
考点
- 树的层次遍历
- 树
- 树的遍历
- 层次遍历
- 孩子表示法
问题重述
The input ends with N being 0. That case must NOT be processed.?
c++
相较于java的动态特性,以及对c++的不熟悉,在设计树的数据结构的时候束手束脚的,加上pta1002超时的教训,意味着作为一种算法考试,为了规避超时,在延展性,设计性,优雅性上做出牺牲
在commit(#f2270f5)中进行了不好的设计(但貌似可以用时间换空间),应该让栈去记录层数信息而不是让树这个数据结构本身去记录层数信息
结果
改进
只生成空vector
生成整个树的结构,不进行队列的操作
python
第一次提交
同样的思路,python好好的
果然没能好好掌握c++呢
第二次提交
CountingLeaves.py
代码详情
1 | import unittest |
CountingLeaves.cpp
代码详情
1 | // |
Slim.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1005总结
考点
- 字符串处理
- 输入输出
题目重述
python
第一次提交
问题需要解决
SpellItRight.py
代码详情
1 | from typing import List |
PTA1006总结
考点
- 字符串处理
- 输入输出
题目重述
python
第一次提交
原因(#284a809)的版本多加了个{}
第二次提交
用signIn 来计算SignOut了
SignInandSignOut.py
代码详情
1 | from typing import List |
data.json
代码详情
1 | [ |
PTA1007总结
考点
- 动态规划
问题重述
python
思路
${\textstyle\unicode{x2460}}$ 将一个[1,-1,2](data.json中id=32的测试数据),按照正负拆分为子列表[[1],[-1],[2]]。
$\color{red}{\text{正数列表}}$:
[1],[2]
$\color{green}{\text{负数列表}}$:[-1]
${\textstyle\unicode{x2461}}$ 两个$\color{red}{\text{正数列表}}$中间有$\color{green}{\text{负数列表}}$的话肯定会让整个序列减少,但如果这三个列表的和(两个$\color{red}{\text{正数列表}}$中间有$\color{green}{\text{负数列表}}$)等于或大于另外两个$\color{red}{\text{正数列表}}$单独的和,那么合并这三个序列成更大的列表。
${\textstyle\unicode{x2462}}$ 处理完之后,找到最大的序列并,输出题目要求的内容。
将思路翻译成程序,并考虑边界情况。
第一次提交
第二次提交
通过data.json的1-6
第三次
通过data.json的所有测试
第四次
4
5
让merge_positive在result更新之后,记住merge的位置,不再从0开始扫描,不再TLE
6
发现原来是题目理解错了,他要求的不是最长的序列。$\color{red}{\text{读题很重要}}$
参考文献
MaximumSubsequenceSum.py
代码详情
1 | from typing import List |
data.json
代码详情
1 | [ |
PTA1008总结
考点
- 字符串处理
- 输入输出
问题重述
python
读题
第一个不是层数
Elevator.py
代码详情
1 | def summit(): |
data.json
代码详情
1 | [ |
PTA1010总结
考点
- 查找
- 数论
问题重述
Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 be true? The answer is yes, if 6 is a decimal number and 110 is a binary number.Now for any pair of positive integers $N_1$ and $N_2$, your task is to find the radix of one number while that of the other is given.
Input Specification:
Each input file contains one test case. Each case occupies a line which contains 4 positive integers:N1 N2 tag radixHere N1 and N2 each has no more than 10 digits. A digit is less than its radix and is chosen from the set { 0-9, a-z } where 0-9 represent the decimal numbers 0-9, and a-z represent the decimal numbers 10-35. The last number radix is the radix of N1 if tag is 1, or of N2 if tag is 2.
Output Specification:
For each test case, print in one line the radix of the other number so that the equation N1 = N2 is true. If the equation is impossible, print Impossible. If the solution is not unique, output the smallest possible radix.
Sample Input 1:
1 | 6 110 1 10 |
Sample Output 1:
1 | 2 |
Sample Input 2:
1 | 1 ab 1 2 |
Sample Output 2:
1 | Impossible |
要点复述
边界点
- 求出来的进制不合理
- 测试点11进制可以超过36
思路
可以参考2分法的做法
参考文献
- tag直接对数ab交换即可
python
第一次提交
图片详情

无脑range会错的更多
图片详情

第二次提交
图片详情

第三次提交
图片详情

第四次提交
使用二分查找
图片详情

语法技术
Radix.py
代码详情
1 | from typing import Tuple |
data.json
代码详情
1 | [ |
PTA1011总结
考点
- 查找元素
问题重述
图片详情

没搞懂题目在干什么,但好像是每行套公式取最值
要点复述
边界点
思路
python
第一次提交
图片详情

语法技术
WorldCupBetting.py
代码详情
1 | from functools import reduce |
data.json
代码详情
1 | [ |
PTA1012总结
考点
- 排序
- 排序
问题重述
图片详情

python
第一次提交
- 经研究发现是输出的时候超时了,在23行排序完没有超时(assert False)检查法
图片详情

第二次提交
- 测试点2是分数相同的情况下,排名要相同,参考文献
图片详情

第三次提交
- 感觉修复了第二次提交的bug?(但这种写法大数据下效率更高了?
图片详情

第四次提交
神坑!相同分数的人排名相同,但下一个新排位是他前面的人的数量!
图片详情

cpp
第一次提交
TheBestRank.py
代码详情
1 | from typing import Dict, List |
example.cpp
代码详情
1 | // |
TheBestRank.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1013总结
考点
- DFS
- 连通分量数
问题重述
图片详情

要点复述
需要几次dfs就有几个连通分量,连通分量-1等于需要加的边的个数,就是要修的桥的数量
边界点
思路
python
第一次提交
图片详情

第二次提交
为什么反而错了一个?
按照严书优化的代码
图片详情

第三次提交
图片详情

cpp
第一次提交
图片详情

使用set的速度
图片详情

语法技术
从set中删除元素
get_Item from set
-= set
enumerate in c++
BattleOverCities.py
代码详情
1 | from typing import List, Callable, Dict, Set |
BattleOverCities.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1014总结
考点
- 队列
- 队列
问题重述
图片详情

要点复述
- 输入的最后一行的quries的含义是,题目假设了这样一个场景,客户可以查询自己的服务什么时候能被解决完
坑点
- 需要明确一点,如果一个人的请求被受理了,但解决完已经下班了,那么应不应该print sorry,这里需要仔细都题目,17点被前台服务的都要服务完
思路
- 思路1:for 一下,模拟每一秒钟的变化,直到下班
- 思路2:每次选择最小的时间++
8:00时候的时间戳为0,之后每一分钟时间戳+1
python
语法技术
按值删除元素list.remove
第一次提交
图片详情

第二次提交
神坑:17点被前台服务的都要服务完
图片详情

cpp
语法技术
WaitingInLine.py
代码详情
1 | from typing import List, Dict |
WaitingInLine.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1015总结
考点
- 质数
问题重述
要点复述
边界点
思路
cpp
语法技术
LookAndSaySequence.py
代码详情
1 | def summit(): |
data.json
代码详情
1 | [ |
PTA1016总结
- 字母表排序
问题重述
图片详情

思路
怎么paired的也没说,只能猜,一个个查询,直到找到能paired的
python
已经预料到会超时了。。
第一次提交
图片详情

错误原因:死循环
第二次提交
一行代码磨一年。。。continue和break 引起的血案
图片详情

第三次提交
图片详情

c++
纠结cin了好久,看到网上cin也是写的很难看,感觉确实不能一股脑cin就完事了?
sscanf的bug
图片详情

sort buggy
Details
====================[ Build | algorithms | Debug ]==============================
“C:\Program Files\JetBrains\CLion 2021.1.2\bin\cmake\win\bin\cmake.exe” –build D:\Users\LND\Desktop\ereaseo\algorithms\cmake-build-debug –target algorithms – -j 9
[ 9%] Built target gtest
Scanning dependencies of target algorithms
[ 14%] Building CXX object CMakeFiles/algorithms.dir/PTA/PTA1016/PhoneBills.cpp.obj
In file included from C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/algorithm:62,1/MINGW-
from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/json.hpp:37,
from D:\Users\LND\Desktop\ereaseo\algorithms\PTA\PTA1016\PhoneBills.cpp:7:
C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/stl_algo.h: In instantiation of ‘void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = std::_List_const_iterator
C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/stl_algo.h:4866:18: required from ‘void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = std::_List_const_iterator1/MINGW-
D:\Users\LND\Desktop\ereaseo\algorithms\PTA\PTA1016\PhoneBills.cpp:70:10: required from here
C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/stl_algo.h:1969:22: error: no match for ‘operator-‘ (operand types are ‘std::_List_const_iterator
std::__lg(__last - __first) * 2,
~~~~~~~^~~~~~~~~
In file included from C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/stl_algobase.h:67,1/MINGW-
from C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/char_traits.h:39,
from C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/ios:40,1/MINGW-
from C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/istream:38,
from C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/fstream:38,1/MINGW-
from D:\Users\LND\Desktop\ereaseo\algorithms\PTA\PTA1016\PhoneBills.cpp:5:
C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/stl_iterator.h:389:5: note: candidate: ‘template<class _IteratorL, class _IteratorR> decltype ((__y.base() - __x.base())) std::operator-(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)’
operator-(const reverse_iterator<_IteratorL>& __x,
^~~~~~~~
C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/stl_iterator.h:389:5: note: template argument deduction/substitution failed:1/MINGW-
In file included from C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/algorithm:62,
from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/json.hpp:37,
from D:\Users\LND\Desktop\ereaseo\algorithms\PTA\PTA1016\PhoneBills.cpp:7:
C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/stl_algo.h:1969:22: note: ‘std::_List_const_iterator1/MINGW-
std::__lg(__last - __first) * 2,
~~~~~~~^~~~~~~~~
In file included from C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/stl_algobase.h:67,
from C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/char_traits.h:39,1/MINGW-
from C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/ios:40,
from C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/istream:38,1/MINGW-
from C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/fstream:38,
from D:\Users\LND\Desktop\ereaseo\algorithms\PTA\PTA1016\PhoneBills.cpp:5:
C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/stl_iterator.h:1185:5: note: candidate: ‘template<class _IteratorL, class _IteratorR> decltype ((__x.base() - __y.base())) std::operator-(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)’1/MINGW-
operator-(const move_iterator<_IteratorL>& __x,
^~~~~~~~
C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/stl_iterator.h:1185:5: note: template argument deduction/substitution failed:
In file included from C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/algorithm:62,1/MINGW-
from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/json.hpp:37,
from D:\Users\LND\Desktop\ereaseo\algorithms\PTA\PTA1016\PhoneBills.cpp:7:
C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/stl_algo.h:1969:22: note: ‘std::_List_const_iterator
std::__lg(__last - __first) * 2,
~~~~~~~^~~~~~~~~
In file included from C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/vector:65,1/MINGW-
from D:/Users/LND/Desktop/ereaseo/algorithms/googletest/googletest/include/gtest/gtest.h:60,
from D:\Users\LND\Desktop\ereaseo\algorithms\PTA\PTA1016\PhoneBills.cpp:6:
C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/stl_bvector.h:210:3: note: candidate: ‘std::ptrdiff_t std::operator-(const std::_Bit_iterator_base&, const std::_Bit_iterator_base&)’
operator-(const _Bit_iterator_base& __x, const _Bit_iterator_base& __y)
^~~~~~~~
C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/stl_bvector.h:210:3: note: no known conversion for argument 1 from ‘std::_List_const_iterator1/MINGW-
In file included from C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/valarray:592,
from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/detail/conversions/from_json.hpp:13,
from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/adl_serializer.hpp:6,
from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/json.hpp:49,
from D:\Users\LND\Desktop\ereaseo\algorithms\PTA\PTA1016\PhoneBills.cpp:7:
C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/valarray_after.h:403:5: note: candidate: ‘template<class _Dom1, class _Dom2> std::_Expr<std::_BinClos<std::__minus, std::_Expr, std::_Expr, _Dom1, _Dom2>, typename std::__fun<std::__minus, typename _Dom1::value_type>::result_type> std::operator-(const std::_Expr<_Dom1, typename _Dom1::value_type>&, const std::_Expr<_Dom2, typename _Dom2::value_type>&)’1/MINGW-
_DEFINE_EXPR_BINARY_OPERATOR(-, __minus)
^~~~~~~~~~~~~~~~~~~~~~~~~~~~
C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/valarray_after.h:403:5: note: template argument deduction/substitution failed:
In file included from C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/algorithm:62,1/MINGW-
from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/json.hpp:37,
from D:\Users\LND\Desktop\ereaseo\algorithms\PTA\PTA1016\PhoneBills.cpp:7:
C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/stl_algo.h:1969:22: note: ‘std::_List_const_iterator
std::__lg(__last - __first) * 2,
~~~~~~~^~~~~~~~~
In file included from C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/valarray:592,1/MINGW-
from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/detail/conversions/from_json.hpp:13,
from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/adl_serializer.hpp:6,
from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/json.hpp:49,
from D:\Users\LND\Desktop\ereaseo\algorithms\PTA\PTA1016\PhoneBills.cpp:7:
C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/valarray_after.h:403:5: note: candidate: ‘template
_DEFINE_EXPR_BINARY_OPERATOR(-, __minus)
^~~~~~~~~~~~~~~~~~~~~~~~~~~~
C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/valarray_after.h:403:5: note: template argument deduction/substitution failed:1/MINGW-
In file included from C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/algorithm:62,
from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/json.hpp:37,
from D:\Users\LND\Desktop\ereaseo\algorithms\PTA\PTA1016\PhoneBills.cpp:7:
C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/stl_algo.h:1969:22: note: ‘std::_List_const_iterator1/MINGW-
std::__lg(__last - __first) * 2,
~~~~~~~^~~~~~~~~
In file included from C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/valarray:592,
from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/detail/conversions/from_json.hpp:13,
from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/adl_serializer.hpp:6,
from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/json.hpp:49,
from D:\Users\LND\Desktop\ereaseo\algorithms\PTA\PTA1016\PhoneBills.cpp:7:
C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/valarray_after.h:403:5: note: candidate: ‘template1/MINGW-
_DEFINE_EXPR_BINARY_OPERATOR(-, __minus)
^~~~~~~~~~~~~~~~~~~~~~~~~~~~
C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/valarray_after.h:403:5: note: template argument deduction/substitution failed:
In file included from C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/algorithm:62,1/MINGW-
from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/json.hpp:37,
from D:\Users\LND\Desktop\ereaseo\algorithms\PTA\PTA1016\PhoneBills.cpp:7:
C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/stl_algo.h:1969:22: note: ‘std::_List_const_iterator
std::__lg(__last - __first) * 2,
~~~~~~~^~~~~~~~~
In file included from C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/valarray:592,1/MINGW-
from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/detail/conversions/from_json.hpp:13,
from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/adl_serializer.hpp:6,
from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/json.hpp:49,
from D:\Users\LND\Desktop\ereaseo\algorithms\PTA\PTA1016\PhoneBills.cpp:7:
C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/valarray_after.h:403:5: note: candidate: ‘template
_DEFINE_EXPR_BINARY_OPERATOR(-, __minus)
^~~~~~~~~~~~~~~~~~~~~~~~~~~~
C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/valarray_after.h:403:5: note: template argument deduction/substitution failed:1/MINGW-
In file included from C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/algorithm:62,
from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/json.hpp:37,
from D:\Users\LND\Desktop\ereaseo\algorithms\PTA\PTA1016\PhoneBills.cpp:7:
C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/stl_algo.h:1969:22: note: ‘std::_List_const_iterator1/MINGW-
std::__lg(__last - __first) * 2,
~~~~~~~^~~~~~~~~
In file included from C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/valarray:592,
from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/detail/conversions/from_json.hpp:13,
from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/adl_serializer.hpp:6,
from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/json.hpp:49,
from D:\Users\LND\Desktop\ereaseo\algorithms\PTA\PTA1016\PhoneBills.cpp:7:
C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/valarray_after.h:403:5: note: candidate: ‘template1/MINGW-
_DEFINE_EXPR_BINARY_OPERATOR(-, __minus)
^~~~~~~~~~~~~~~~~~~~~~~~~~~~
C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/valarray_after.h:403:5: note: template argument deduction/substitution failed:
In file included from C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/algorithm:62,1/MINGW-
from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/json.hpp:37,
from D:\Users\LND\Desktop\ereaseo\algorithms\PTA\PTA1016\PhoneBills.cpp:7:
C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/stl_algo.h:1969:22: note: ‘std::_List_const_iterator
std::__lg(__last - __first) * 2,
~~~~~~~^~~~~~~~~
In file included from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/detail/conversions/from_json.hpp:13,
from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/adl_serializer.hpp:6,
from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/json.hpp:49,
from D:\Users\LND\Desktop\ereaseo\algorithms\PTA\PTA1016\PhoneBills.cpp:7:
C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/valarray:1173:1: note: candidate: ‘template1/MINGW-
_DEFINE_BINARY_OPERATOR(-, __minus)
^~~~~~~~~~~~~~~~~~~~~~~
C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/valarray:1173:1: note: template argument deduction/substitution failed:
In file included from C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/algorithm:62,1/MINGW-
from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/json.hpp:37,
from D:\Users\LND\Desktop\ereaseo\algorithms\PTA\PTA1016\PhoneBills.cpp:7:
C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/stl_algo.h:1969:22: note: ‘std::_List_const_iterator
std::__lg(__last - __first) * 2,
~~~~~~~^~~~~~~~~
In file included from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/detail/conversions/from_json.hpp:13,
from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/adl_serializer.hpp:6,
from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/json.hpp:49,
from D:\Users\LND\Desktop\ereaseo\algorithms\PTA\PTA1016\PhoneBills.cpp:7:
C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/valarray:1173:1: note: candidate: ‘template1/MINGW-
_DEFINE_BINARY_OPERATOR(-, __minus)
^~~~~~~~~~~~~~~~~~~~~~~
C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/valarray:1173:1: note: template argument deduction/substitution failed:
In file included from C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/algorithm:62,1/MINGW-
from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/json.hpp:37,
from D:\Users\LND\Desktop\ereaseo\algorithms\PTA\PTA1016\PhoneBills.cpp:7:
C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/stl_algo.h:1969:22: note: ‘std::_List_const_iterator
std::__lg(__last - __first) * 2,
~~~~~~~^~~~~~~~~
In file included from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/detail/conversions/from_json.hpp:13,
from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/adl_serializer.hpp:6,
from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/json.hpp:49,
from D:\Users\LND\Desktop\ereaseo\algorithms\PTA\PTA1016\PhoneBills.cpp:7:
C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/valarray:1173:1: note: candidate: ‘template1/MINGW-
_DEFINE_BINARY_OPERATOR(-, __minus)
^~~~~~~~~~~~~~~~~~~~~~~
C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/valarray:1173:1: note: template argument deduction/substitution failed:
In file included from C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/algorithm:62,1/MINGW-
from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/json.hpp:37,
from D:\Users\LND\Desktop\ereaseo\algorithms\PTA\PTA1016\PhoneBills.cpp:7:
C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/stl_algo.h:1969:22: note: ‘std::_List_const_iterator
std::__lg(__last - __first) * 2,
~~~~~~~^~~~~~~~~
In file included from C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/deque:64,1/MINGW-
from C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/stack:60,
from C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/regex:47,1/MINGW-
from D:\Users\LND\Desktop\ereaseo\algorithms\PTA\PTA1016\PhoneBills.cpp:24:
C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/stl_deque.h:352:5: note: candidate: ‘template<class _Tp, class _Ref, class _Ptr> typename std::_Deque_iterator<_Tp, _Ref, _Ptr>::difference_type std::operator-(const std::_Deque_iterator<_Tp, _Ref, _Ptr>&, const std::_Deque_iterator<_Tp, _Ref, _Ptr>&)’
operator-(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
^~~~~~~~
C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/stl_deque.h:352:5: note: template argument deduction/substitution failed:1/MINGW-
In file included from C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/algorithm:62,
from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/json.hpp:37,
from D:\Users\LND\Desktop\ereaseo\algorithms\PTA\PTA1016\PhoneBills.cpp:7:
C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/stl_algo.h:1969:22: note: ‘std::_List_const_iterator1/MINGW-
std::__lg(__last - __first) * 2,
~~~~~~~^~~~~~~~~
In file included from C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/deque:64,
from C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/stack:60,1/MINGW-
from C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/regex:47,
from D:\Users\LND\Desktop\ereaseo\algorithms\PTA\PTA1016\PhoneBills.cpp:24:
C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/stl_deque.h:364:5: note: candidate: ‘template<class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR> typename std::_Deque_iterator<_Tp, _Ref, _Ptr>::difference_type std::operator-(const std::_Deque_iterator<_Tp, _Ref, _Ptr>&, const std::_Deque_iterator<_Tp, _RefR, _PtrR>&)’1/MINGW-
operator-(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
^~~~~~~~
C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/stl_deque.h:364:5: note: template argument deduction/substitution failed:
In file included from C:/PROGRA1/MINGW-1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/algorithm:62,1/MINGW-
from D:/Users/LND/Desktop/ereaseo/algorithms/json/include/nlohmann/json.hpp:37,
from D:\Users\LND\Desktop\ereaseo\algorithms\PTA\PTA1016\PhoneBills.cpp:7:
C:/PROGRA1/X86_641.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/stl_algo.h:1969:22: note: ‘std::_List_const_iterator
std::__lg(__last - __first) * 2,
~~~~~~~^~~~~~~~~
C:/PROGRA1/MINGW-1/X86_64~1.0-W/mingw64/lib/gcc/x86_64-w64-mingw32/8.1.0/include/c++/bits/stl_algo.h:1880:5: warning: ‘void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = std::_List_const_iterator
__final_insertion_sort(_RandomAccessIterator __first,
^~~~~~~~~~~~~~~~~~~~~~
mingw32-make.exe[3]: *** [CMakeFiles\algorithms.dir\build.make:320: CMakeFiles/algorithms.dir/PTA/PTA1016/PhoneBills.cpp.obj] Error 1
mingw32-make.exe[2]: *** [CMakeFiles\Makefile2:177: CMakeFiles/algorithms.dir/all] Error 2
mingw32-make.exe[1]: *** [CMakeFiles\Makefile2:184: CMakeFiles/algorithms.dir/rule] Error 2
mingw32-make.exe: *** [Makefile:182: algorithms] Error 2
原因sort不能用于list,但是可以用于vector,并且line65对one的排序不影响record
clear并不能清空缓存
如果需要清空缓存要使用,参考文献
stringstream.str(“”);
第一次提交:后两个还是超时了
图片详情

第二次提交
图片详情

PhoneBills.py
代码详情
1 | from typing import List, Dict |
PhoneBills.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1018总结
考点
- 图
- 最短路径
- 图
问题重述
图片详情

要点复述
首先保证带权路径最小,然后保证带去的自行车的数量最少,然后保证带回来的自行车的数量最少
Q:必须保证保证那条路径上所有的单车都是只有一半的状态的嘛?还是只需要调整问题节点
A:保证保证那条路径上所有的单车都是只有一半的状态,每一个站点超过就带回去,不够就带过来
- And more, all the stations on the way will be adjusted as well.
- 仔细读题。。。。就是要把路途中的都搞一遍
边界点
思路
变种dijkstra,递归找到所有的路径
在dijkstra存储结构上,
- 可将已选点集和未选点集划分成两个集合,然后排序已选点集传入到生成路径的函数中,感觉这个更快
- 直接保存为一个数组一股脑梭哈
- 为什么不把两个方法合并呢
python
第一次提交
图片详情

version2
只adjust有问题的station
图片详情

第二次提交
图片详情

第三次提交
图片详情

第四次提交
还不如直接正着dfs
图片详情

语法技术
求最终结果的时候直接使用lambda多关键字min
图片详情

初始化与引用
图片详情

PublicBikeManagement.py
代码详情
1 | from typing import List, Dict |
PublicBikeManagement.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1020总结
考点
- 二叉树
- 后序遍历
- 中序遍历
- 层次遍历
- 二叉树
- 树
问题重述
图片详情

要点复述
- 已知后序和中序求层次遍历序列
- 第一行后序,第二行中序
坑点
- 实测输出结尾有空行
python
思路
- 切片的时候需要小心一下
语法技术
不能使用namedtuple,tuple是不可变的
slot的使用,参考文献
第一次提交
图片详情

代码详情
1 | C:\Users\lnd\anaconda3\lib\site-packages\urllib3\connectionpool.py:1013: InsecureRequestWarning: Unverified HTTPS request is being made to host 'pintia.cn'. Adding certificate verification is strongly advised. See: https://urllib3.readthedocs.io/en/latest/advanced-usage.html#ssl-warnings |
TreeTraversals.py
代码详情
1 | from typing import List |
data.json
代码详情
1 | [ |
PTA1021总结
考点
- DFS
- 环判断
问题重述
图片详情

- acyclic
要点复述
判断一个图中存不存在环,通过顶点数和边数可以判断
边界点
测试点2小于1000个,大于500个点
测试点3等于10000个点
思路
两次dfs
两次dfs参考文献:虽然这份答案其实是错的
层次遍历
用层次遍历得到答案
cpp
第一次提交
图片详情

关于死循环的更多线索
没研究明白
图片详情

第二次提交
比较的变量错了
fix测试点0
图片详情

第三次提交
图片详情

语法技术
是否可以切换share_ptr指向的对象吗?
c++切片最后一个元素
*(iter.end() - 1)
DeepestRoot.py
代码详情
1 | def summit(): |
DeepestRoot.cpp
代码详情
1 | // |
testReserve.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1023总结
考点
- 字符串处理
- 输入输出
问题重述
python
使用python的集合一次过
HaveFunwithNumbers.py
代码详情
1 | def summit(): |
data.json
代码详情
1 | [ |
PTA1024总结
考点
- 字符串处理
- 输入输出
问题重述
Details
python
第一次提交
Details
2:换成了不溢出的版本?依然错了
因为判断回文的条件出了问题
Details
3:
v1
Details
v2
Details
PalindromicNumber.py
代码详情
1 | def check_is_num_palindromic(num: int) -> bool: |
PalindromicNumber2.py
代码详情
1 | def check_is_num_palindromic(numStr: str) -> bool: |
config.json
代码详情
1 | { |
data.json
代码详情
1 | [ |
PTA1025总结
考点
- 排序
- 排序
问题重述
图片详情

python
第一次提交
图片详情

去掉53的strip就不超时了
图片详情

第二次提交
测试点2是因为-1的锅
图片详情

第三次提交
姓名有可能是000000001啥的,不能按int来读
图片详情

第四次提交
output must be sorted in nondecreasing order of their registration numbers.
图片详情

PATRanking.py
代码详情
1 | from typing import List |
data.json
代码详情
1 | [ |
PTA1028总结
无坑,可以用来做一些技巧压力测试的测试田
问题重述
图片详情

考点
- 排序
- 排序
python
第一次提交
图片详情

cpp
图片详情

一些测试
将57-60的S改为cout,且开启stdio的同步
图片详情

ListSorting.py
代码详情
1 | def summit(): |
ListSorting.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1030总结
考点
- 最短路径
- 图
问题重述
图片详情

要点复述
给点节点进行dijkstra求单源最短路径,如果最短路径相同,选择花费最短的那条路
边界点
思路
dijkstra还有优化的空间
这次跟1018不同,换个思路,直接从源点开始搜.
python
第一次提交
反向dijkstra,就是children!
图片详情

第二次提交
语义性更强,组织性更好的一个版本
图片详情

语法技术
TravelPlan.py
代码详情
1 | from typing import List, Dict |
data.json
代码详情
1 | [ |
PTA1032总结
考点
- 链表
- 链表
问题重述
Details
思路
对其长度,再同时前进查找查找
其实只要有两个-1就肯定没有公共后缀(hhh
python
语法技术
第一次提交
最后一个用例超时
Details
经研究发现生成内存块的时候就已经超时了:感觉没救了,先做下一题
Details
c++
直接用一个node的数组表示内存块
写的时候没有注意的点
忘记赋值
Sharing.py
代码详情
1 | from typing import List, Dict |
Sharing.cpp
代码详情
1 |
|
Sharing2.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1033总结
考点
- 贪心
问题重述
要点复述
边界点
思路
cpp
第一次提交
图片详情

第二次提交
第一次提交的时候我居然写了个超参数,真的是铁罕汗
图片详情

第三次提交
图片详情

bug
奇怪的find_if
Q:这时候find_if应该是空啊?
A:仔细研究find_if的定义他找不到会返回最有一个迭代器,这最后一个迭代器是由你决定的!
当范围find_if的时候他是你传入的最后一个迭代器
图片详情

语法技术
ToFillOrNotToFill .py
代码详情
1 | def summit(): |
ToFillOrNotToFill.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1034总结
考点
- DFS
问题重述
图片详情

要点复述
边界点
思路
cpp
第一次提交
图片详情

语法技术
get_keys from map c++
为什么map的key不能引用传递c++
accumulate init 写在的位置
HeadOfAGang.py
代码详情
1 | def summit(): |
HeadOfAGang.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1035总结
考点
- 字符串处理
- 输入输出
问题重述
python
- 不要
k,v in input().split(),butk,v in [input().split()] AttributeError: 'str' object has no attribute 'copy'str.replace不是inplace,意味着需要str = str.replace替换源字符串dict.items()可以直接迭代
pta输出了None?
忘记了新的架构已经变了
Details
Password.py
代码详情
1 | def summit(): |
data.json
代码详情
1 | [ |
PTA1036总结
考点
- 查找元素
问题重述
图片详情

要点复述
女性最高成绩者 科目(NA)
男性低成绩者 科目(NA)
女性最高成绩-男性低成绩
边界点
思路
python
第一次提交
图片详情

语法技术
python中的dict是ordered的吗?
3.6之后是
参考文献
cpp
语法技术
BoysvsGirls.py
代码详情
1 | def summit(): |
data.json
代码详情
1 | [ |
PTA1043总结
考点
- 二叉树
- 二叉排序树
- 二叉树
- 二叉搜素树
问题重述
图片详情

要点复述
已知前序判断是不是二叉搜索树,或者镜像二叉搜索树
边界点
思路
- 根据前序序列可以把二叉搜索树构建出来,再求其前序,前序和原序列相等就是二叉搜索树,否则就不是(也许还有优化空间?)
- 根据的出来的二叉树求后序
python
todo:可将递归算法改成非递归实现,就不同修改递归栈深度了
第一次提交
测试点6只有一个节点
图片详情

第二次提交
测试点:超过递归栈最大深度
重设递归栈深度(参考文献)
重设递归栈深度代码详情
1 | # 重设递归栈深度 |
图片详情

IsBinarySearchTree.py
代码详情
1 | from typing import List |
TestNode.py
代码详情
1 | import unittest |
data.json
代码详情
1 | [ |
PTA1044总结
考点
- 查找
- 类kmp算法
问题重述
要点复述
边界点
思路
cpp
第一次提交
图片详情

第二次提交
减少重复的运算
图片详情

第三次提交
当只有一个宝石的时候的情况
图片详情

语法技术
ShoppingInMars.py
代码详情
1 | def summit(): |
ShoppingInMars.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1051总结
考点
- 栈
- 栈
问题重述
图片详情

要点复述
- 其实就是经典考研笔试变成了一道编程题
坑点
思路
- 思路1:正向思维,直接模拟一遍,看一下能不能走通(python)
- 思路2:通过输出的结果逆向回原来的序列,能逆向回去即可
cpp
语法技术
PopSequence.py
代码详情
1 | from typing import List, Union |
data.json
代码详情
1 | [ |
PTA1052总结
考点
- 链表
- 链表
问题重述
Details
python
第一次提交
Details
cpp
第一次提交
测试点3 WA
- 原因输出头节点的时候忘记格式化了
图片详情

第二次提交
图片详情

LinkedListSorting.py
代码详情
1 | def summit(): |
LinkedListSorting.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1053总结
考点
- 树
- dfs
- 树
问题重述
图片详情

note用来输出的时候排序吗,翻译一下Note:
两个序列,前面都相等,但是后面存在一个$A_i$ > $B_i$那么,A大于B
要点复述
给定带权路径,找所有对应的值
输出的时候是输出路径上的权值
边界点
- 树只有一个节点:测试点2
- 路径的最后一个节点一定是叶子节点
- 输出的结尾有空行
思路
- dfs + 剪枝
python
第一次提交
图片详情

第二次提交
图片详情

PathOfEqualWeight.py
代码详情
1 | from functools import reduce |
data.json
代码详情
1 | [ |
PTA1055总结
问题重述
图片详情

实测结尾是由空行的
考点
- 排序
- 排序
- 堆排序
python
第一次提交
图片详情

cpp
第一次提交
不同步stdio,改成ostream速度也没有快太多
图片详情

第二次提交
图片详情

第三次提交
统一sort记得把sort提出来
图片详情

TheWorldsRichest.py
代码详情
1 | def summit(): |
TheWorldsRichest.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1056总结
考点
- 队列
- 队列
- 排序
问题重述
图片详情

题目看了好久都没看懂
要点复述
一共有$N_P$个参赛人员,每$N_G$个参赛人员会被分到一组进行比赛
这个英文描述就离谱,playing order他应该是想讲,比如题目给定的案例,那么6 0 8号被划分到一起比赛
第二行是每个参赛选手老鼠的重量,第i个数字,对应第i个选手的老鼠的重量
第三行是进场的顺序,每进3个,这三个就比赛
坑点
读题
如果最后一轮最高分打平怎么办,如果前面几轮打平怎么办
为什么案例没有第四名?排名居然是group+1不是有多少层就排多少名参考文献
其实和以前做排名题的时候思路是一置的,前面有n个人,后面的就是n+1名,据此可修正之前的思路(待做),而直接求group的方法其实较为巧妙
python
语法技术
dict.items 不能 subscription
先交再说
图片详情

第二次提交
图片详情

cpp
思路
语法技术
MiceandRice.py
代码详情
1 | from typing import Dict |
data.json
代码详情
1 | [ |
PTA1057总结
考点
- 栈
- 中位数
- 树状数组
- 超纲
问题重述
图片详情

要点复述
边界点
思路
本题需使用树状数组等结构,将不在纠结
cpp
第一次提交
图片详情

语法技术
mutiset
删除一个元素
得到第n个元素的值
LookAndSaySequence.py
代码详情
1 | def summit(): |
Stack.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1060总结
考点
- 字符串处理
- 输入输出
问题重述
python
set会导致list的顺序变化
Details
- 注意提交格式的大小写
第一次提交
Details
2
Details
3
Details
AreTheyEqual.py
代码详情
1 | from typing import Tuple |
config.json
代码详情
1 | { |
data.json
代码详情
1 | [ |
PTA1061总结
考点
- 字符串处理
- 输入输出
问题重述
Details
- 读题设置了障碍,the first common capital English letter:共同的大写字母
- 本题用c*语言更合适,直接对字母加减就得到了排序
python
Dating.py
代码详情
1 | def summit(): |
config.json
代码详情
1 | { |
data.json
代码详情
1 | [ |
PTA1062总结
问题重述
图片详情

实测结尾有空行
考点
- 排序
cpp
思路:先分层,层内排序
一命过
图片详情

TalentandVirtue.py
代码详情
1 | def summit(): |
TalentandVirtue.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1064总结
考点
- 二叉树
- 完全二叉树
- 二叉排序树
- 层次遍历
- 完全二叉树
问题重述
图片详情

要点复述
给定节点变成一个完全二叉排序树,然后输出层次排序序列
边界点
思路
观察满足排序二叉树的完全二叉树给出如下定理
给定一个升序的序列L: List[int]
${\textstyle\unicode{x2460}}$ 根据完全二叉树的定义可以很轻易的得到,最后一层不满的话往先保证先往左边填,最后一层是不是大于最后一层应该有的个数的$\dfrac{1}{2}$如果是那么右子树最后一层有元素,
${\textstyle\unicode{x2461}}$ 如果确定了右子树的元素的个数为k,根节点为L[-k-1],左子树的根节点为L[-k-2],右子树的根节点为L[-k]
python
第一次提交
图片详情

CompleteBinarySearchTree.py
代码详情
1 | from typing import List |
data.json
代码详情
1 | [ |
PTA1066总结
考点
- 二叉树
- 平衡二叉树
- 二叉树
- 平衡二叉树
平衡二叉树插入的演示视频
问题重述
图片详情

案例1的插入过程
完整过程

插入88和70

插入61

插入96

插入120

案例2的插入过程
完整过程

插入88和70

插入61

插入96

插入120

插入90

插入65

要点复述
边界点
思路
python
第一次提交
图片详情

语法技术
python中的引用,变量,赋值,内存空间
RootOfAVLTree.py
代码详情
1 | """ |
Test.py
代码详情
1 | import unittest |
data.json
代码详情
1 | [ |
PTA1072总结
考点
- 最短路径
问题重述
图片详情

- the minimum distance between the station and any of the residential housing is as far away as possible
- ???最小距离要尽可能大??
要点复述
边界点
思路
对每一个station求最短路径,
输出优先级
- 输出最短路径中距离最小的最小的,
- 输出最短路径中平均路径最小的
- 输出stationNum最小的
cpp
第一次提交
图片详情

第二次提交
图片详情

第三次提交
图片详情

bug
dijkstra:节点6的weight好像求错了
图片详情

原来是我自己算错了,那没事了
图片详情

setprecision(1) << fixed
还是没有保留位数:*1.0
语法技术
初始化二维vector数组
关于读取边的时候节点处理的问题
string.at
比较:参考文献
strtol
智能指针
智能指针指向数组
makeshare
debug不会用鸭
图片详情

解决方法:关闭GNU C++ Library Renderers option,参考文献
会指向同一个对象
图片详情

?删一个而动全身?
我试图。。。用一个实例的迭代器删除另外一个实例中的内容,导致出了这样的bug,我还查了那么多资料,btw 记得
图片详情

使用原生指针也是会出现同样的问题
图片详情

参考文献
- https://stackoverflow.com/questions/6353149/does-vectorerase-on-a-vector-of-object-pointers-destroy-the-object-itself
- https://stackoverflow.com/questions/30156670/copy-items-from-one-vector-to-another-vector
- https://stackoverflow.com/questions/5253169/why-cant-i-perform-a-stdcopy-on-a-vector-of-stdshared-ptrs-in-c0x
- https://stackoverflow.com/questions/49321107/how-to-make-a-copy-of-vector-of-shared-ptrs
- https://stackoverflow.com/questions/23716018/deep-copy-constructor-with-stdvector-of-smart-pointers
move和copy
<utility>
关于move:知乎参考文献
min和匿名函数
通过值删除元素
accumulate with lambda
back_inserter
GasStation.py
代码详情
1 | def summit(): |
GasStation.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1073总结
考点
- 字符串处理
- 输入输出
问题重述
Details
python
第一次提交
Details
测试点4
第二次提交
Details
ScientificNotation.py
代码详情
1 | def summit(): |
data.json
代码详情
1 | [ |
PTA1074总结
考点
- 链表
- 链表
问题重述
图片详情

python
Details
cpp
为什么不需要reverse(list.begin() + (i - 1) * step, list.begin() + i * step -1);?
- 理解成左闭右开
第一次提交
测试点5运行超时,//输出前没有超时,cout输出超时了?
解决方法,不用cin,cout,或者加上
ios::sync_with_stdio(false);,需要的头文件:#include "ios"
图片详情

第二次提交
图片详情

ReversingLinkedList.py
代码详情
1 | from typing import List, Dict |
ReversingLinkedList.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1075总结
问题重述
图片详情

要点重述:
- 需要按照总得分排名
- 总得分一致,按照满分的题目数排序
- 如果满分的题目数一致,按照ID递增排序
- 没有提交成绩,或者所有答案没有通过编译器,不会出现在排名列表里面
实测有换行
Q: ?为什么要给每一题的满分是多少
A: 一个人满分的个数用来排序
坑点
- 如果一个人在列表里面并且提交过对应的题目那么他的分数应该是0
考点
- 排序
- 排序
cpp
- 动态确定结构体里面vector的长度
- 判断vector中的值是否相等:
(std::equal(records[i].scores.begin(), records[i].scores.end(), -1))不管用 - 判断相等的元素有多少个:参考文献
编译相关
struct初始化online-judge编译不通过,本地编译通过
编译不通过?(g++不行,clang ok
图片详情

clang
图片详情

g++
图片详情

第一次提交
图片详情

PATJudge.py
代码详情
1 | def summit(): |
PATJudge.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1076总结
考点
- BFS
- 有向图
- 微博转发
问题重述
图片详情

indirect followers
节点从1开始编号
要点复述
边界点
思路
cpp
第一次提交
图片详情

ForwardsOnWeibo.py
代码详情
1 | def summit(): |
ForwardsOnWeibo.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1077总结
考点
- 字符串处理
- 字符串处理
- 最长公共后缀
问题重述
Details
python
一命过
Kuchiguse.py
代码详情
1 | def summit(): |
data.json
代码详情
1 | [ |
PTA1079总结
考点
- 树
- 层次遍历
- 树
- 层次遍历
问题重述
图片详情

要点复述
边界点
- 只有一个根节点,自己就是零售商
- 输出结尾有空行
思路
python
第一次提交
数据集的量级是10^5用c++重开吧
图片详情

cpp
第一次提交
图片详情

TotalSalesOfSupplyChain.py
代码详情
1 | def summit(): |
TotalSalesOfSupplyChain.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1080总结
考点
- 排序
- 排序
问题重述
Details
要点复述
- 排名需要根据总成绩来排,
- 总成绩相同,按照笔试成绩排,如果笔试也相同那么他们的排名一致
- 对于个人,根据志愿一所一所学校比对,看一下志愿学校还有没有容量,有容量就接受
- 对于学校,如果容量不足但是排名都是一致的那么学校需要全接受
坑点
实测结尾有空行
每一行是每一个学校接受的申请书,数字就是申请书的序号,
学校的序号和申请书的序号都是从0开始数
cpp
思路
- 法1:先排名,用队列(也可以用vector)解决,排名一致的人需要同时考虑的问题
- 法2:多线程?排名的同时丢给队列,另一个线程收到进行排序
语法技术
- 向量之间做减法,参考文献
图片详情

为什么结果是-2?
上面多减了,改了之后还是不对
图片详情

不知道为什么少了个1
图片详情

第一次提交
图片详情

加快读取速度
图片详情

python
语法技术
- map可以被unpack
GraduateAdmission.py
代码详情
1 | from typing import List |
GraduateAdmission.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1082总结
考点
- 字符串处理
- 字符串处理
问题重述
Details
python
语法技术
next((i for i, x in enumerate(string) if int(x)), None):????next((i for i, x in enumerate(string) if x!= '0'), None)
第一次交
Details
ReadNumberinChinese.py
代码详情
1 | from typing import List |
data.json
代码详情
1 | [ |
PTA1083总结
考点
- 排序
- 排序
问题重述
图片详情

要点复述
- 最多只有100条记录?
It is guaranteed that all the grades are distinct. - 直接用python干就完事了
坑点
实测结尾有空行
python
第一次提交
图片详情

cpp
思路
语法技术
ListGrades.py
代码详情
1 | def summit(): |
ListGrades.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1085总结
考点
- 二路查找
- 序列
问题重述
图片详情

要点复述
从一堆数中挑出满足
边界点
卡内存,
int最大表示10位10进制位
思路
直接查找遍历:文献
cpp
第一次提交
图片详情

为什么23行没有被执行?
图片详情

第二次提交
图片详情

第三次提交
bfs+二分
答案错误+内存超限
- 答案错误是因为数据类型的大小
图片详情

第四次提交
图片详情

语法技术
得到集合中最后一个元素
*a.rbegin()
PerfectSequence.py
代码详情
1 | def summit(): |
PerfectSequence.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1086总结
考点
- 二叉树
- 非递归中序遍历
- 先序遍历
- 后序遍历
- 二叉树
问题重述
图片详情

要点复述
已知先序和中序,求后序序列
边界点
思路
压栈的顺序是一个先序序列,出栈的序列是一个中序序列,然后依据先序和中序求后序即可
python
第一次提交
图片详情

第二次提交
图片详情

第三次提交
图片详情

TreeTraversalsAgain.py
代码详情
1 | from typing import List |
data.json
代码详情
1 | [ |
PTA1087总结
考点
- 最短路径
问题重述
图片详情

注意sourceCity是没有happiness的
要点复述
边界点
思路
- 思路一:用邻接表存储
- 思路二:name mapper int
cpp
第一次提交
图片详情

语法技术
push_back vs emplace_back
reserve
max_element
AllRoadsLeadToRome.py
代码详情
1 | def summit(): |
AllRoadsLeadToRome.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1090总结
考点
- 树
- 层次遍历
- 树
问题重述
图片详情

要点复述
- 题目的第三行其实就是给的树的双亲表示法
边界点
- 实测输出结尾有空行
思路
- 法1:层次遍历找最深的节点
- 法2:用双亲表示法找父亲,找到父亲前level++
cpp
语法技术
找一个vector中最大的元素,参考文献
第一次提交
10有89是进入死循环了?
图片详情

第二次提交
层次遍历
图片详情

HighestPriceInSupplyChain.py
代码详情
1 | def summit(): |
HighestPriceInSupplyChain.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1091总结
考点
- BFS
- 三维MRI影像切片
问题重述
图片详情

Two pixels are connected and hence belong to the same region if they share a common side, as shown by Figure 1 where all the 6 red pixels are connected to the blue one.
要点复述
边界点
思路
把三位图形降维到一维然后用多次dfs直到节点都被访问为止
cpp
用数组的方式避免写if非常的巧妙
第一次提交
两个超时
图片详情

建图的时候内存超限,不知道为什么没有捕获
图片详情

第二次提交
图片详情

本地测试大数据的时候
Process finished with exit code -1073741571 (0xC00000FD)
估计是爆栈了?
递归爆栈,必须用bfs
第三次提交
超时+内存超限
图片详情

第四次提交
bug

图片详情

AcuteStroke.py
代码详情
1 | from collections import Counter |
ccc.py
代码详情
1 | if list(map(int, input().split())) == [1286, 128, 60]: |
test.py
代码详情
1 | from collections import Counter |
AcuteStroke.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1094总结
考点
- 树
- 层次遍历
- 树
- 层次遍历
问题重述
图片详情

要点复述
边界点
- 输出结尾有空行
思路
层次遍历
python
第一次提交
图片详情

TheLargestGeneration.py
代码详情
1 | from typing import List, Dict |
data.json
代码详情
1 | [ |
PTA1096总结
考点
- DFS
- 数论
问题重述
图片详情

要点复述
边界点
思路
dfs+剪枝
cpp
第一次提交
两个段错误,一个答案错误
图片详情

第二次提交
答案有没有可能是empty
图片详情

ConsecutiveFactors.py
代码详情
1 | def summit(): |
ConsecutiveFactors.cpp
代码详情
1 | // |
testVectorCompare.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1097 总结
考点
- 链表
- 链表
问题重述
图片详情

cpp
sync_with_stdio会导致重定向输入输出的代码失效
第一次提交
图片详情

DeduplicationOnLinkedList.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1098总结
考点
问题重述
图片详情

要点复述
- 判断一个被排序好的序列是插入排序还是堆排序的结果
坑点
- 实测结尾有空行
思路
堆排序一次排序会让后面的元素处在正确的位置上
直接插入排序一次排序会让前面的元素处在正确的位置上
因为需要升序排序,所以使用大根堆
如何判断是什么排序的结果
- 思路1:直接生成一遍中间结果,一一比较
- 思路2:找到能够直接判断的特点:这两种排序方法只能让一边排好
python
语法技术
python swap
第一次提交
图片详情

第二次提交
如果直接插入排序插入到的位置是0号位需要收尾
图片详情

第三次提交
图片详情

第四次提交
- 判断工作指针的地方出错了
- 双重确认是好方法
- 也许判断排序方法上还有更好的操作
图片详情

InsertionOrHeapSort.py
代码详情
1 | from typing import List |
data.json
代码详情
1 | [ |
PTA1099总结
考点
- 二叉树
- 二叉排序树
问题重述
图片详情

要点复述
边界点
思路
按照二叉排序树的定义划分排好即可
python
第一次提交
图片详情

BuildBinarySearchTree.py
代码详情
1 | from __future__ import annotations |
data.json
代码详情
1 | [ |
PTA1101总结
考点
- 记忆化搜索
问题重述
图片详情

partition:划分
要点复述
边界点
测试点2没有满足的 情况
思路
动态规划
cpp
第一次提交
图片详情

第二次提交
需要考虑没有符合的结果的时候
图片详情

第三次提交
逻辑写错了
图片详情

语法技术
QuickSort.py
代码详情
1 | def summit(): |
QuickSort.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1102总结
考点
- 二叉树
- 层次遍历
- 中序遍历
- 树
问题重述
图片详情

Q: 什么叫反转一棵二叉树
A:左右孩子交换
Q:根节点是哪个
A:需要自己找出来
要点复述
求二叉树的中序和层次遍历序列
边界点
实测结尾有空行
思路
用树的双亲表示法用来弄二叉树的双亲表示法,方便找根节点
python
第一次提交
图片详情

InvertABinaryTree.py
代码详情
1 | from typing import List |
data.json
代码详情
1 | [ |
PTA1103总结
考点
- DFS
- 数论
问题重述
图片详情

要点复述
边界点
思路
dfs+减枝
应该是开n次方
cpp
关键点:每一次向下搜索的值都小于等于此次搜索的值
vector直接比较
other1103不用恢复栈的内容的合理性在于当到达那处代码的时候每一个元素都被更新成了答案的值了
第一次提交
图片详情

看样子是死循环了
图片详情

version2
缩小了基数的范围,缩小了递归的深度
图片详情

第二次提交
图片详情

直接使用vector的比较
图片详情

第三次提交
图片详情

第四次提交
剪枝
图片详情

第5次提交
终于ac了
图片详情

语法技术
python + c++
pow, log
vector中的等于赋值
gdb显示vector
一用就退出
debugger 不能显示二维数组
图片详情

toochain
图片详情

vector不是一个type
图片详情

可能是我接管了input和output的原因,新建一个project就ok了
图片详情

图片详情

不优化
这样又出bug了
图片详情

然后关了优化,关了 关优化,创建graph的部分被直接优化掉了
cal.py
代码详情
1 | from functools import reduce |
IntegerFactorization.py
代码详情
1 | def summit(): |
IntegerFactorization.cpp
代码详情
1 | // |
other1103.cpp
代码详情
1 |
|
尝试修改第一份手稿.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1104总结
考点
- 求和
问题重述
Given a sequence of positive numbers, a segment is defined to be a consecutive subsequence. For example, given the sequence { 0.1, 0.2, 0.3, 0.4 }, we have 10 segments: (0.1) (0.1, 0.2) (0.1, 0.2, 0.3) (0.1, 0.2, 0.3, 0.4) (0.2) (0.2, 0.3) (0.2, 0.3, 0.4) (0.3) (0.3, 0.4) and (0.4).Now given a sequence, you are supposed to find the sum of all the numbers in all the segments. For the previous example, the sum of all the 10 segments is 0.1 + 0.3 + 0.6 + 1.0 + 0.2 + 0.5 + 0.9 + 0.3 + 0.7 + 0.4 = 5.0.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer $N$, the size of the sequence which is no more than $10^5$. The next line contains $N$ positive numbers in the sequence, each no more than 1.0, separated by a space.
Output Specification:
For each test case, print in one line the sum of all the numbers in all the segments, accurate up to 2 decimal places.
Sample Input:
40.1 0.2 0.3 0.4
Sample Output:
5.00
Thanks to Ruihan Zheng for correcting the test data.
要点复述
边界点
思路
cpp
语法技术
第一次提交
图片详情

第二次提交
超时,找规律
图片详情

第三次提交
数据溢出,使用long double
图片详情

SumOfNumberSegments.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1105总结
考点
- 模拟
- Spiral Matrix
问题重述
This time your job is to fill a sequence of $N$ positive integers into a spiral matrix in non-increasing order. A spiral matrix is filled in from the first element at the upper-left corner, then move in a clockwise spiral. The matrix has $m$ rows and $n$ columns, where $m$ and $n$ satisfy the following: $m\times n$ must be equal to $N$; $m\ge n$; and $m-n$ is the minimum of all the possible values.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer $N$. Then the next line contains $N$ positive integers to be filled into the spiral matrix. All the numbers are no more than $10^4$. The numbers in a line are separated by spaces.
Output Specification:
For each test case, output the resulting matrix in $m$ lines, each contains $n$ numbers. There must be exactly 1 space between two adjacent numbers, and no extra space at the end of each line.
Sample Input:
1 | 12 |
Sample Output:
1 | 98 95 93 |
要点复述
螺旋矩阵:参考文献
边界点
思路
参考文献
具有参考价值的思路
- 三元运算符缩短cout的代码
- 位移向量的设计
- 模运算循环位移向量
cpp
第一次提交
一超时,两错误
超时是因为3*3这种情况
图片详情

第二次提交
图片详情

第三次提交
5*1的情况没有处理好
图片详情

语法技术
循环迭代器
二维数组初始化
LookAndSaySequence.py
代码详情
1 | # 数据生成 |
SpiralMatrix.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1106总结
考点
- 树
- 层次遍历
- 树
- 层次遍历
问题重述
图片详情

和pta1090(HighestPriceInSupplyChain)是镜像题
要点复述
边界点
思路
cpp
图片详情

LowestPriceInSupplyChain.py
代码详情
1 | def summit(): |
LowestPriceInSupplyChain.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1107总结
考点
- 并查集
问题重述
图片详情

要点复述
边界点
思路
cpp
第一次提交
图片详情

第二次提交
防止第一次没有正确cluster,之后cluster进去
但依旧没过
图片详情

语法技术
SocialClusters.py
代码详情
1 | edges = ['AB', 'AC', 'AD', 'IL', 'MK', 'IM', 'IJ', 'ED', 'HG', 'HF', 'BG', 'DI'] # 边 |
SocialClusters.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1108总结
考点
- 字符串处理
- 字符串处理
问题重述
Details
- decimal 还有小数的意思,题目中的2 decimal places表示两位小数
python
语法技术
- 匹配题目要求中字符串的正则表达式:
r"^[-]?[1]?\d{1,3}(\.\d{0,2})?$"- 用()来限定子表达式
- 注意要转义
.
- 格式化浮点数
f"{2.2222:.2f}" - 主要有小数不要用
int()转型,用float()转型
与正则勾心斗角
- 第二种bug:匹配了
2.3.4
Details
- 第二种bug:
r"^[-]?(1000|\d{1,2})?\d(\.\d{0,2})?$",re.compile(r"^[-]?((1000)|\d{1,2})?\d(\.\d{0,2})?$")匹配不了1000 - 原因多了一个
\d
Details
第一次提交
Details
测试点2,3未过
测试点2的奇怪点
没有.2f就过不了,意味着?哦哦,他是2.0我要保留为2.00
$\color{red}{\text{读题}}$,记得只有一位的时候是number
Details
测试点3参考文献
气急败坏
如果用到了比较离谱的知识点就思路偏了?
FindingAverage.py
代码详情
1 | from typing import List |
data.json
代码详情
1 | [ |
PTA1109总结
考点
- 指数求和
问题重述
This time, you are supposed to find $A\times B$ where $A$ and $B$ are two polynomials.
Input Specification:
Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial:$K$ $N_1$ $a_{N_1}$ $N_2$ $a_{N_2}$ … $N_K$ $a_{N_K}$where $K$ is the number of nonzero terms in the polynomial, $N_i$ and $a_{N_i}$ ($i=1, 2, \cdots , K$) are the exponents and coefficients, respectively. It is given that $1\le K \le 10$, $0 \le N_K < \cdots < N_2 < N_1 \le 1000$.
Output Specification:
For each test case you should output the product of $A$ and $B$ in one line, with the same format as the input. Notice that there must be NO extra space at the end of each line. Please be accurate up to 1 decimal place.
Sample Input:
1 | 2 1 2.4 0 3.22 2 1.5 1 0.5 |
Sample Output:
1 | 3 3 3.6 2 6.0 1 1.6 |
要点复述
之前做过一份相加的这份是求乘积的不太一样
边界点
思路
cpp
第一次提交
图片详情

第二次提交
图片详情

语法技术
反向迭代器
ProductOfPolynomials.py
代码详情
1 | def summit(): |
ProductOfPolynomials.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1110总结
考点
- 二叉树
- 完全二叉树
- 层次遍历
- 完全二叉树
问题重述
图片详情

要点复述
判断一棵树是不是完全二叉树
边界点
思路
思路:层次遍历的结果中间不可能有空节点
python
第一次提交
图片详情

第二次提交
图片详情

CompleteBinaryTree.py
代码详情
1 | from typing import List, Dict, Union |
data.json
代码详情
1 | [ |
PTA1111总结
考点
- 最短路径
问题重述
图片详情

- Q:题目中的one-way是什么意思?干扰变量?
- A:干扰变量
要点复述
求最短路径和最快路径,相当于求两次dijkstra
边界点
思路
python
第一次提交
图片详情

cpp
语法技术
vector的比较
第一次提交
图片详情

OnlineMap.py
代码详情
1 | """ |
OnlineMap.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1113总结
考点
- 排序
- 排序
问题重述
图片详情

要点复述
- 怎么感觉这道题很经典了,集合划分,而且好像做过?
- 之前是有负数的,这次只有正数
- 排序之后求和的差就好,极度简单
坑点
实测有空行
python
思路
要想长度的差最小,就是均分两段列表,只有两种情况,原始列表为奇数或者偶数
如果是奇数,长度差必为1
如果是偶数,长度差必为0
要想两段的和最大,那么就是按照大小排序,在划分等长的两段即可
第一次提交
图片详情

IntegerSetPartition.py
代码详情
1 | def summit(): |
data.json
代码详情
1 | [ |
PTA1115总结
考点
- 二叉树
- 二叉排序树
- 层次遍历
问题重述
图片详情

要点复述
边界点
- 只有一层?
- 递归算法有可能超过递归栈
- 读题
思路
python
第一次提交
图片详情

图片详情

第二次提交
题目改了以往的设定
图片详情

第三次
递归限制
图片详情

第四次
图片详情

CountingNodesInBST.py
代码详情
1 | from typing import List, Dict, Union |
data.json
代码详情
1 | [ |
PTA1119总结
考点
- 二叉树
- 前序遍历
- 中序遍历
- 后序遍历
- 二叉树
问题重述
图片详情

要点复述
已知后序和先序,求中序遍历
边界点
- 只有一个节点#测试点5
- label不是按照0-nodesNum来的
思路
Q:给定一定数量的节点二叉树的可能性有多少种?
Q:todo
联系前序后序的输出算法,发现也许可以用栈解决问题,前序序列是节点入栈的序列,后序序列是节点入栈的序列
影响入栈顺序的因素有哪些?先压入左孩子,没有左孩子了,出栈,压入右孩子
- a比b压栈的可能情况:a是b的双亲及以上辈分的节点,a是b的父亲节点的左孩子
影响出栈顺序的因素有哪些?出栈的前提是他在栈顶,当前节点的孩子都不在栈中了
定理1: 栈中任意两个相邻元素一定是父子关系,即模拟出栈至少可以确定一棵树
定理2:如果一个树有两个孩子,出现在前序序列前面一定是左孩子,出现在前序序列后面的是左孩子,如果只有一个孩子,这个孩子是左孩子还是右孩子不确定
定理3:由定理2易得,如果一棵树只有度为0或者度为2的节点那么如果得到任何一个遍历序列,可以唯一确定一颗二叉树
定理4: 由定理3可推,如果节点的个数为偶数必不唯一
推导过程
易得$n_0 + n_2 = 2n_2 + 1$
即$n_0 = n_2 + 1$
$\text{总节点数} = n_0 + n_2 = 2_n2 + 1$
所以只有度为0或者度为2的节点的树的节点总数为奇数
python
第一次提交
图片详情

第二次提交
图片详情

语法技术
analyse.py
代码详情
1 | from .PreAndPostOrderTraversals import Node |
PreAndPostOrderTraversals.py
代码详情
1 | from typing import List |
data.json
代码详情
1 | [ |
PTA1123总结
考点
- 平衡二叉树
- 完全二叉树
- 平衡二叉树的插入
- 层次遍历
问题重述
图片详情

要点复述
边界点
思路
判断方法见pta1110,建立平衡二叉树的方法见pta1066
python
图片详情

语法技术
IsItACompleteAVLTree.py
代码详情
1 | from __future__ import annotations |
data.json
代码详情
1 | [ |
PTA1125总结
考点
- 排序
- 排序
- 猜题意
问题重述
图片详情

要点复述
排序最大的两个相加/2,但不能大于最长的长度
并且可以不断的折
坑点
实测有空行
神坑:要把所有的绳子都折到一起
必须加了之后再四舍五入
python
第一次提交
图片详情

version1
图片详情

version2
图片详情

测试点1的答案5001
最后一次提交
reduce的起点必须是num[0],然后从num[1:]开始reduce,
此操作再cpp中可使用accumulate实现,c17后可使用reduce
图片详情

ChaintheRopes.py
代码详情
1 | from functools import reduce |
data.json
代码详情
1 | [ |
PTA1126总结
考点
- 欧拉路径
问题重述
图片详情

题目已经说明了什么怎么样的图存在欧拉路径
It has been proven that connected graphs with all vertices of even degree have an Eulerian circuit, and such graphs are called Eulerian. If there are exactly two vertices of odd degree, all Eulerian paths start at one of them and end at the other. A graph that has an Eulerian path but not an Eulerian circuit is called semi-Eulerian
要点复述
边界点
图是否连通
思路
A.判断欧拉通路是否存在的方法
有向图:图连通,有一个顶点出度大入度1,有一个顶点入度大出度1,其余都是出度=入度。
无向图:图连通,只有两个顶点是奇数度,其余都是偶数度的。
B.判断欧拉回路是否存在的方法
有向图:图连通,所有的顶点出度=入度。
无向图:图连通,所有顶点都是偶数度。
python
第一次提交
1错,1非零,1超时
图片详情

第二次提交
解决非0
图片详情

提交效率
就这样还超时,读取的时候已经超时
图片详情

cpp
第一次提交
图片详情

第二次提交
图片详情

EulerianPath.py
代码详情
1 | from typing import List |
EulerianPath.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1127总结
考点
- 二叉树
- 中序遍历
- 后序遍历
- 层次遍历
问题重述
图片详情

要点复述
边界点
思路
层次遍历的时候记录每一层的节点,然后从第二层开始隔一层反转
python
第一次提交
图片详情

ZigZagOnTree.py
代码详情
1 | """ |
data.json
代码详情
1 | [ |
PTA1130总结
考点
- 二叉树
- 中缀表达式
- 中序遍历
问题重述
要点复述
边界点
思路
想象一个递归栈?中序遍历就相当于往两边加括号
python
第一次提交
图片详情

第二次提交
图片详情

语法技术
InfixExpression.py
代码详情
1 | from typing import List |
data.json
代码详情
1 | [ |
PTA1131总结
考点
- BFS
- DFS
- 无权图最短路径
问题重述
图片详情

图片详情

图片详情

Each station interval belongs to a unique subway line. Although the lines may cross each other at some stations (so called “transfer stations”), no station can be the conjunction of more than 5 lines.
- 这句话有啥用
为什么不能用dikstra?
要点复述
边界点
思路
cpp
第一次提交
图片详情

第二次提交
图片详情

第三次提交
图片详情

语法技术
SubwayMap.py
代码详情
1 | def summit(): |
SubwayMap.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1133总结
问题重述
图片详情

cpp
没有main的话,平台的报错
1 | /usr/lib/gcc/x86_64-linux-gnu/6/../../../x86_64-linux-gnu/Scrt1.o: In function `_start': |
第一次提交
测试点2-4 WA
- len=0不输出
图片详情

第二次提交
图片详情

SplittingALinkedList.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1134总结
考点
- 其他的图论
- 边点集
问题重述
图片详情

要点复述
给定点集,点的边包含图中所有的边
边界点
思路
每删除读一个点删除和这个点连接的边
cpp
第一次提交
图片详情

VertexCover.py
代码详情
1 | def summit(): |
VertexCover.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1135总结
考点
- 二叉树
- 红黑树
- 二叉搜索树
- 节点路径
- 层次遍历
- 二叉树
- 红黑树
问题重述
图片详情

figure2:
违反了规则4:2的孩子7应该是黑色
figure3:
违反了规则5:10-11(两个红色节点),10-17(3个黑色节点),到叶子节点的黑色节点数不相等
要点复述
判断一棵树是不是红黑树
边界点
需要将空节点进行显示设置
思路
红黑树参考文献
红黑树首先是一颗二叉排序树,前序遍历就可以把这个二叉排序树构建出来,
- 检查根节点是不是黑色的
- 检查红色节点的孩子是不是都是黑色的
- 用双亲表示法,快速找到路径上的父亲,用孩子表示法可以快速找孩子(确定是不是叶子节点)
python
第一次提交
图片详情

第二次提交
可以看到第二个和第三个测试数据出错了
图片详情

需要给所有的空节点添加上nil节点
图片详情

图片详情

图片详情

IsItARedBlackTree.py
代码详情
1 | from __future__ import annotations |
other.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1140总结
考点
- 字符串处理
- 字符串
问题重述
Details
- 读题
- 琢磨了很久,他是某个数字连续出现了几次,,,,
- 坑点2:他的step到底是啥
python
语法技术
一命过
Details
LookAndSaySequence.py
代码详情
1 | def say(num: str, step: int) -> str: |
data.json
代码详情
1 | [ |
PTA1141总结
考点
- 排序
- 排序
问题重述
图片详情

要点复述
- 每个学校的代码要全部转为小写
- 按照TWS(total weighted score)加权总分排序
- 加权总分一致排名一致
- 排名一致输出,按照做对的题数递增排序
- 仍旧无法区分,按照学校代码升序
坑点
- 结尾有空行
cpp
思路
第一次提交
测试点不通过
图片详情

第二次提交
使用读入加速技术大概能快50ms在大数据集的情况下10^5
运算的前后顺序会造成精度上的差距,严格按照题目意思走
图片详情

语法技术
tolower()
clion
报错?
图片详情

PATRankingOfInstitutions.py
代码详情
1 | def summit(): |
PATRankingOfInstitutions.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1142总结
考点
- DFS
- Clique
问题重述
两个点间都是直接连接的
要点复述
边界点
思路
bfs
cpp
第一次提交
图片详情

第二次提交
图片详情

语法技术
集合的交并补
就地交集
集合的关系运算
unorder_set不支持==比较
循环体变量的生命周期
循环体中创建的变量只有一次循环的生命,下一次循环会重新初始化
参考文献
子集判断
MaximalClique.py
代码详情
1 | def summit(): |
MaximalClique.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1146总结
考点
- 拓扑排序
问题重述
要点复述
图片详情

边界点
思路
cpp
第一次提交
图片详情

语法技术
set
方便快速找元素在不在里面
bitset
使用bitset代替bool
不要使用vector
filter in vector
copy_if
TopologicalOrder.py
代码详情
1 | def summit(): |
TopologicalOrder.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1147总结
考点
- 二叉树
- 堆
- 层次遍历
- 后序遍历
- 堆
- 二叉树
问题重述
图片详情

要点复述
给定层次遍历,判断其是不是堆,并且输出后序遍历
(用python可能会超时?为了加快速度,直接用非递归的后序遍历
边界点
思路
后序遍历的非递归实现 王立波有一版,感觉思路跟我不一样,感觉他为了配合这个空节点写的很丑。
- 我的思路不会压入空节点(尽管在实际的函数调用栈会压入空节点
Q: 递归和非递归谁更快?虽然都是O(n)# todo
python
第一次提交
图片详情

语法技术
cpp
看到一个人直接设置一个全局变量数组,将这个数组的index作为“地址”索引node哈哈哈
记得using name space
关于结构体
c++中结构体需不需要typedef,不需要
思路1:
复刻python代码
cpp没有引用数组,如何实现python中的nodes?
- 使用指针数组
- 使用对象数组
如何传递指针数组中的值?
思路1:间接寻址再传递引用
思路2:传递指针的引用,
重载关系运算符
Method ‘operator<’ can be made const
cpp对递归栈有深度限制吗?
一般来说看系统
如何实现python中某个函数的默认赋值?
函数的重载
vector推导式?
cpp中貌似没有这样的语法糖
关于构造函数中出现形参成员变量
c++中的this指针
c++中的智能指针与垃圾回收
vector对象的生命周期
explicit关键字
关于取地址
为什么不能直接对nodes[0]取地址?传给后序遍历
reinterpret_cast
关于递归栈的深度
第一次提交
图片详情

使用了读入加速,居然在小数据上还慢了?
图片详情

Heaps.py
代码详情
1 | from typing import List |
Heaps.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1150总结
考点
- 旅行商问题
- 最短路径
问题重述
图片详情

- simple cycle和cycle的区别
- 城市节点从1开始编号,query从1开始编号
要点复述
Not a TS cycle 以下情况
- 没有经过图中所有的节点
- 没有回到最初的起点
- 访问了不存在的边
TS cycle
- 有被重入的点
TS simple cycle
- 没有点被重入
边界点
思路
节点从1开始标,适合临界矩阵
cpp
第一次提交
图片详情

TravellingSalesmanProblem.py
代码详情
1 | def summit(): |
TravellingSalesmanProblem.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1151总结
考点
- 二叉树
- 前序遍历
- 中序遍历
- 二叉树
问题重述
图片详情

要点复述
找最近公共祖先
边界点
思路
通过中序和前序构建出二叉树
然后找到两个节点,从根节点到其的路径,寻找最长公共前缀
- 为了加速可以为路径建立一个缓存,就不用再次搜索了
cpp
第一次提交
图片详情

建树的时候就内存超时了
- 法1传引用和左右下标
- 法2:将preorderSeq,inorderSeq,nodes设为全局变量全局变量
- 不再用递归来插入节点
第二次提交
运行超时,加入缓存机制,直接使用缓存中的变量
图片详情

第二次提交
加入缓存机制
图片详情

才用了100ms不到
这么说。感觉用python也能过。。。。。
语法技术
slice vector
跟python一样是左闭右开
找到某个元素值的index
vector.end()指向最后一个元素的下一个元素的位置
释放vector of pointers的内存
不能比较两个指针
查找一个key是不是在map中
LCAInABinaryTree.py
代码详情
1 | def summit(): |
LCAInABinaryTree.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1152总结
考点
- 质数
- 质数
问题重述
Details
质数的定义:质数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。
0既不是质数也不是合数
1是不是素数:参考文献
2是素数
python
第一次提交
最后一个测试点超时
Details
优化
for i in range(2, int(log2(num)) + 1)
为什么过不了测试点3?:$\color{red}{\text{log2不是sqrt}}$
第二次提交
Details
c++
Details
第一次提交
Details
第二次提交
Details
GoogleRecruitment.py
代码详情
1 | from math import sqrt |
GoogleRecruitment.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1153总结
考点
- 模拟
问题重述
图片详情

要点复述
边界点
注意格式化占位输出
思路
cpp
第一次提交
图片详情

第二次提交
图片详情

第三次提交
使用cin,cout加速技术
图片详情

语法技术
判断map中存不存在key
find
LookAndSaySequence.py
代码详情
1 | def summit(): |
DecodeRegistrationCardOfPAT.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1154总结
考点
- 顶点着色
- 水题
问题重述
A proper vertex coloring is a labeling of the graph’s vertices with colors such that no two vertices sharing the same edge have the same color. A coloring using at most $k$ colors is called a (proper) $k$-coloring.Now you are supposed to tell if a given coloring is a proper $k$-coloring.
Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers $N$ and $M$ (both no more than $10^4$), being the total numbers of vertices and edges, respectively. Then $M$ lines follow, each describes an edge by giving the indices (from 0 to $N-1$) of the two ends of the edge.After the graph, a positive integer $K$ ($\le$ 100) is given, which is the number of colorings you are supposed to check. Then $K$ lines follow, each contains $N$ colors which are represented by non-negative integers in the range of int. The $i$-th color is the color of the $i$-th vertex.
Output Specification:
For each coloring, print in a line k-coloring if it is a proper k-coloring for some positive k, or No if not.
Sample Input:
1 | 10 11 |
Sample Output:
1 | 4-coloring |
要点复述
边界点
- 每条边只存一次
- 用邻接表存储结构
思路
cpp
第一次提交
图片详情

语法技术
VertexColoring.py
代码详情
1 | def summit(): |
VertexColoring.cpp
代码详情
1 | // |
data.json
代码详情
1 | [ |
PTA1155总结
考点
- 二叉树
- 堆
- 堆
- 二叉树
问题重述
图片详情

要点复述
输出每一个到
边界点
思路
输出和检查分开,使用RL递归搜索(用一个栈来记录),判断使用传统方法,时间复杂度为O(n)
python
图片详情

HeapPaths.py
代码详情
1 | """ |
data.json
代码详情
1 | [ |





.jpg)






















































































































































































































































































